package fun.coding.leetcode;

public class StrStr {

	public static void main(String[] args) {
		StrStr ins = new StrStr();
		System.out.println(ins.strStr("abbcd", "bc"));
	}
	
	public int strStr1(String haystack, String needle) {
		// TODO: known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, and the Boyer- Moore algorithm.
		// http://blog.csdn.net/v_july_v/article/details/7041827
		return -1;
	}
	
	public int strStr(String haystack, String needle) {
		if (haystack == null || needle == null) return -1;
		
		int l = haystack.length();
		int res = -1;
		
		// This is still O^2, but did prune some unnecessary computation
		// for (int i = 0; i < l ; i++) {
		for (int i = 0; i < l - needle.length() + 1; i++) {
			int index = i;
			int j = 0; 
			
			while (j < needle.length() && index < l) {
				if (haystack.charAt(index) != needle.charAt(j)) break;
				
				j++;
				index++;
			}
			
			if (j == needle.length()) return i;
			
		}
		
		return res;
	}

}
